#ifndef LINKED_LIST_H_
#define LINKED_LIST_H_

#include <string.h>
#include <Basic.hh>

//
/**
 * \file LinkedList.h
 * \author  jsk <jsk.jinsubkim@gmail.com>
 * \version 1.0
 *
 * \class LinkedList LinkedList.h
 *
 * LinkedList 클래스는 평범한 더블리(doubly) 링크드 리스트 클래스이다.
 * 이 클래스는 클래스나 구조체에 포함되는 방식으로 사용된다. 다시말해서
 * 클래스에 포함되어서 클래스 인스턴스의 주소를 Container에 저장하고
 * 같은 클래스의 다른 인스턴스의 노드와 연결하는 방식이다.
 *
 * \verbatim
 * strcutr A {
 *   ...
 *   LinkedList<A> Node;
 *
 *   A() : Node(this) {}
 * }
 * \endverbatim
 *
 * 리눅스의 프로세스 디스크립트를 모방한 디자인이다. 그리고 연결 형태는
 * ... - [Left] - [Current] - [Right] - ... 형태로 이어진다.
 */
template <class T>

class LinkedList
{
// Interface

public:
	/**
	 * \name LinkedList
	 *
	 * Constructor
	 *
	 * \warning
	 *
	 * 만약 컨테이너의 주소가 NULL이면, 다른 노드와 연결되지 않는다.
	 */
	LinkedList(T* NewContainer)
	{
		Container = NewContainer;
		LeftNode = NULL;
		RightNode = NULL;
	}

	/**
	 * \name ~LinkedList
	 *
	 * Destructor
	 */
	virtual ~LinkedList()
	{
		unlink();
	}

	/**
	 * \name tellContainer
	 *
	 * 자신(노드)을 포함하는 컨테이너의 주소를 반환한다.
	 *
	 * \return
	 *
	 * 컨테이너의 주소.
	 */
	virtual T* tellContainer() const
	{
		return Container;
	}

	/**
	 * \name tellLeftNode
	 *
	 * 윈쪽에 연결된 노드의 주소를 알려준다.
	 *
	 * \return
	 *
	 * 윈쪽 노드의 주소.
	 */
	virtual LinkedList* tellLeftNode() const
	{
		return LeftNode;
	}

	/**
	 * \name tellRightNode
	 *
	 * 오른쪽에 연결된 노드의 주소를 알려준다.
	 *
	 * \return
	 *
	 * 오른쪽 노드의 주소.
	 */
	virtual LinkedList* tellRightNode() const
	{
		return RightNode;
	}

	/**
	 * \name tellLeftContainer
	 *
	 * 윈쪽에 연결된 노드의 컨테이너 주소를 알려준다.
	 *
	 * \return
	 *
	 * 윈쪽 노드의 컨테이너 주소.
	 */
	virtual T *tellLeftContainer() const
	{
		if (LeftNode == NULL)
			return NULL;
		
		return LeftNode->tellContainer();
	}

	/**
	 * \name tellRightContainer
	 *
	 * 오른쪽에 연결된 노드의 컨테이너 주소를 알려준다.
	 *
	 * \return
	 *
	 * 오른쪽 노드의 컨테이너 주소.
	 */
	virtual T *tellRightContainer() const
	{
		if (RightNode == NULL)
			return NULL;
		
		return RightNode->tellContainer();
	}

	/**
	 * \name linkToLeft
	 *
	 * 새로운 노드를 윈쪽에 연결한다.
	 * 만약 이미 윈쪽에 연결된 노드가 있다면 그 사이에 새로운 노드를 삽입한다.
	 *
	 * \warning
	 *
	 * 새로운 노드(NewNode)의 이전 연결은 해제된다.
	 *
	 * \return
	 *
	 * 성공할 경우 RETURN_OK,
	 * 실패할 경우 RETURN_OK가 아닌 값.
	 */
	virtual ResultOf linkToLeft(LinkedList* NewNode)
	{
		if (NewNode == NULL || NewNode->Container == NULL)
			return RETURN_PARAM_ERROR;
		
		NewNode->unlink();
		
		// LeftNode <--> A
		// LeftNode <--> NewNode <--> A
		if (LeftNode != NULL)
		{
			NewNode->setLeftNode(LeftNode);
			LeftNode->setRightNode(NewNode);
		}
		
		NewNode->setRightNode(this);
		
		setLeftNode(NewNode);
		
		return RETURN_OK;
	}

	/**
	 * \name linkToLeft
	 *
	 * 새로운 노드를 오른쪽에 연결한다.
	 *
	 * 만약 이미 오른쪽에 연결된 노드가 있다면 그 사이에 새로운 노드를
	 * 삽입한다.
	 *
	 * \warning
	 *
	 * 새로운 노드(NewNode)의 이전 연결은 해제된다.
	 *
	 * \return
	 *
	 * 성공할 경우 RETURN_OK,
	 * 실패할 경우 RETURN_OK가 아닌 값.
	 */
	virtual ResultOf linkToRight(LinkedList* NewNode)
	{
		if (NewNode == NULL || NewNode->Container == NULL)
			return RETURN_PARAM_ERROR;

		NewNode->unlink();

		// A <--> RightNode
		// A <--> RightNode <--> LeftNode
		if (RightNode != NULL)
		{
			NewNode->setRightNode(RightNode);
			RightNode->setLeftNode(NewNode);
		}

		NewNode->setLeftNode(this);

		setRightNode(NewNode);

		return RETURN_OK;
	}

	/**
	 * \name unlink
	 *
	 * 연결을 해제 한다.
	 * 만약 윈쪽이나 오른쪽에 연결된 노드가 있다면 이 둘을 연결시킨다.
	 */
	virtual void unlink()
	{
		// Left <--> A <--> Right
		// Left <--> Right

		if (LeftNode != NULL)
			LeftNode->setRightNode(RightNode);

		if (RightNode != NULL)
			RightNode->setLeftNode(LeftNode);

		setLeftNode(NULL);

		setRightNode(NULL);
	}

	/**
	 * \name unlinkLeftNode
	 *
	 * 윈쪽 연결만 해제 한다.
	 *
	 * 만약 윈쪽에 연결된 노드가 있다면 윈쪽 노드의 오른쪽 연결을 초기화 한다.
	 */
	virtual void unlinkLeftNode()
	{
		// Left <--> A <--> ...
		// Left      A <--> ...

		if (LeftNode != NULL)
			LeftNode->setRightNode(NULL);

		setLeftNode(NULL);
	}

	/**
	 * \name unlinkLeftNode
	 *
	 * 오른쪽 연결만 해제 한다.
	 *
	 * 만약 오른쪽에 연결된 노드가 있다면 오른쪽 노드의 윈쪽 연결을 초기화
	 * 한다.
	 */
	virtual void unlinkRightNode()
	{
		// ... <--> A <--> Right
		// ... <--> A      Rgiht

		if (RightNode != NULL)
			RightNode->setLeftNode(NULL);

		setRightNode(NULL);
	}

	//! 순회(traversal)에 사용되는 함수의 형태 정의.
	typedef ResultOf(*Fp)(T*, LinkedList*, LinkedList*, LinkedList*);

	/**
	 * \name traverseToLeft
	 *
	 * 현 노드로부터 윈쪽으로 연결된 노드를 순회한다.
	 *
	 * \return
	 *
	 * 성공할 경우 RETURN_OK,
	 * 실패할 경우 RETURN_OK가 아닌 값.
	 */
	virtual ResultOf traverseToLeft(Fp Function)
	{
		ResultOf Result;
		LinkedList* CurrentNode;

		for (CurrentNode = this;
		      CurrentNode != NULL;
		      CurrentNode = CurrentNode->LeftNode)
		{
			Result = Function(CurrentNode->Container,
			                  CurrentNode,
			                  CurrentNode->LeftNode,
			                  CurrentNode->RightNode);

			if (Result != RETURN_OK || CurrentNode == RightNode)
				break;
		}

		return Result;
	}

	/**
	 * \name traverseToRight
	 *
	 * 현 노드로부터 오른쪽으로 연결된 노드를 순회한다.
	 *
	 * \return
	 *
	 * 성공할 경우 RETURN_OK,
	 * 실패할 경우 RETURN_OK가 아닌 값.
	 */
	virtual ResultOf traverseToRight(Fp Function)
	{
		ResultOf Result;
		LinkedList* CurrentNode;

		for (CurrentNode = this;
		      CurrentNode != NULL;
		      CurrentNode = CurrentNode->RightNode)
		{
			Result = Function(CurrentNode->Container,
			                  CurrentNode,
			                  CurrentNode->LeftNode,
			                  CurrentNode->RightNode);

			if (Result != RETURN_OK || CurrentNode == LeftNode)
				break;
		}

		return Result;
	}

// Module

protected:
	/**
	 * \name setLeftNode
	 *
	 * 윈쪽 노드를 지정된 노드로 변경한다.
	 *
	 * \return
	 *
	 * 이전 윈쪽 노드의 주소.
	 */
	virtual LinkedList* setLeftNode(LinkedList *NewNode)
	{
		LinkedList* Return = LeftNode;
		LeftNode = NewNode;

		return Return;
	}

	/**
	 * \name setLeftNode
	 *
	 * 오른쪽 노드를 지정된 노드로 변경한다.
	 *
	 * \return
	 *
	 * 이전 오른쪽 노드의 주소.
	 */
	virtual LinkedList* setRightNode(LinkedList *NewNode)
	{
		LinkedList* Return = RightNode;
		RightNode = NewNode;
		return Return;
	}

// Memboer

protected:
	//! 윈쪽 노드의 주소.
	LinkedList* LeftNode;

	//! 오른쪽 노드의 주소.
	LinkedList* RightNode;

	//! (자신을 포함하는) 컨테이너의 주소.
	T* Container;
};

#endif //LINKED_LIST_H_

